package com.sise.Backtracking;

import java.util.*;


/**
 *      40. 组合总和 II
 *      给定一个数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 *      candidates 中的每个数字在每个组合中只能使用一次。
 *      注意：解集不能包含重复的组合。
 *
 *      示例1:
 *      输入: candidates =[10,1,2,7,6,1,5], target =8,
 *      输出:
 *      [
 *      [1,1,6],
 *      [1,2,5],
 *      [1,7],
 *      [2,6]
 *      ]
 *
 *      在全排列的问题里，相同的数字集合，不同的顺序表示了不同的排列。used 数组表示了哪些数字已经出现过，接下来不能使用；
 *      而组合问题里，由于不强调顺序，包含了一个数字的所有组合得到以后，下一轮搜索就不能再含有这个数字，否则会出现重复。因此需要设置搜索起点 begin。
 *      这点区别表现在 dfs(i, ...)和 dfs(i+1, ...)上。dfs(i+1, ...)可以避免重复使用当前元素。
 */
public class _40_combinationSum2 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 关键步骤
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates, 0, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param begin      从候选数组的 begin 位置开始搜索，同时代表树的层数
     *                   每个数字在每个组合中只能使用一次，故此每次进行递归 dfs() 时，都需要传递 cur + 1，在 for 循环初始化值时需要 cur = begin
     * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
     * @param path       从根结点到叶子结点的路径
     * @param res        结果集
     */
    private void dfs(int[] candidates, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {

        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int cur = begin; cur < candidates.length; cur++) {
            // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
            if (target - candidates[cur] < 0) {
                break;
            }

            // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
            /**
             *  1、排除同一层次： candidates[] 是排序后的数组，使用 candidates[cur] == candidates[cur - 1] 可以剪掉第二个 2 的树枝，因为前面已经有一个树枝为 2 了
             *                    1
             *                  / \
             *                 2   2    假设数组为[1,2,2,5]，那么就会出现如图情况， 此时右边的 2 是 candidates[2] 的数值，此时发现 candidates[1] == candidates[2]
             *                /         说明在前一个书分支已经使用过了
             *               5
             *  2、如果只靠 candidates[cur] == candidates[cur - 1]，那么以下情况也不行了，而实际上应该是可以的
             *                  1
             *                  /
             *                 2
             *                /
             *               2
             *  3、cur 代表当前层，也可以理解为当前的数组索引下标。cur == begin 说明刚递归到这一层，cur > begin 说明已经经过 for 循环
             *     根据观察，可以使用 cur > begin 来避免这种情况，在一个for循环中，所有被遍历到的数都是属于一个层级的。
             *     我们要让一个层级中，必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。
             *     第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是 cur > begin，故此利用此特性把后面的排除掉
             */
            if (cur > begin && candidates[cur] == candidates[cur - 1]) {
                continue;
            }

            path.addLast(candidates[cur]);
            // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
            dfs(candidates, cur + 1, target - candidates[cur], path, res);
            path.removeLast();
        }
    }
}

